In packet-based data networks such as the Internet, routers “talk” to each other to exchange routing information. Specifically, a router will announce the path it will use to get to a particular destination to each of its peer routers. Each router will thus know the path that its peer routers will take in sending a packet to a particular destination. Routing protocols, running on the routers, are used to exchange such information between routers. A routing protocol can be an Internal Gateway Protocol (IGP) or an Exterior Gateway Protocol (EGP).
An IGP is used for routing within an administrative domain such as within a corporate backbone network or within a network that is owned by one company and has a unified administrative control over how routing is done. Such a domain is referred to as an autonomous system (or “AS”). Generally such IGP routing is metric-based in that the goal in routing between two points within an administrative domain is to find the route with the lowest cost, where cost may, for example, be distance or some other parameter that can be assigned to a link between routers. Examples of common IGP routing protocols are the Routing Information Protocol (RIP), the Open Shortest Path First (OSPF) protocol, and the Intermediate System to Intermediate System (IS—IS) protocol. The advantageous property of such IGPs is that they are guaranteed to always achieve a stable routing within the network that is consistent with the network's configuration. The difference between the different routing protocols lies in the nature of the messages passed between routers. Since an IGP is used within a network that is owned or controlled by a single organization, no hostility exists between the owners of the routers within the network that might otherwise affect the willingness of one particular router to accept traffic from another.
An EGP is used to exchange routing information between autonomous systems. Thus, border, or edge, routers that might link, for example, an autonomous AT&T network with an autonomous Sprint network, need to communicate via an EGP rather than an IGP. Unlike a single autonomous system in which routing can be metric based, routing between autonomous systems needs to be policy based. Each autonomous system may in fact want to protect itself from being used by others who are not paying for its use. Thus, one autonomous system may restrict routing through it from a competitor's system since it doesn't want such competitor's customers to use its resources, even though such routing would be the “shortest” path. EGPs, unlike metric-based IGPs, are thus policy based because autonomous systems will not always be able to agree as to the best path to a specified destination. As a result, an EGP is much more complicated to administer since it involves expressing a policy of how an administrative domain wants to interact with the rest of the world.
The Border Gateway Protocol (BGP) is currently the only EGP employed on the Internet (see, e.g., Y. Rekhter and T. Li, “A border gateway protocol”, RFC 1771 [BGP version 4], 1995; J. W. Stewart, BGP4, Inter-Domain Routing in the Internet, Addison-Wesley, 1998; and B. Halabi, Internet Routing Architectures, Cisco Press, 1997). The BGP, which has become a de-facto standard, allows each autonomous system to independently formulate its own routing policies, and it allows these policies to override distance metrics in favor of policy concerns. However, routing policies of autonomous systems can conflict with each other. Inconsistencies in routing policies can result in several problems such as the inability to find a stable routing plan. Thus, as a change at one router occurs, information is exchanged with its peers that causes a second router to change its routing and exchange information with its peer routers, etc., etc., eventually causing the first router to change its routing again, then the second and so forth. In such a case, the protocol is said to diverge and cause a route oscillation. Thus, with the BGP, edge routers between autonomous systems could continue to only exchange information without ever agreeing upon a stable routing plan. Such a situation could in fact have a catastrophic effect in the global Internet resulting in improperly routed traffic, and possibly even causing “gridlock” on the Internet with the amount of routing information being transferred from router to router. The latter could slow the network down to a crawl and, in a worst case situation, could cause a “meltdown” of the Internet. Further, an autonomous system on the network has no ability to determine the cause of the routing problems since it only has local information available to it. Even if it had such an ability, no one autonomous system would have the ability to correct oscillations caused by inconsistency of routing policies between autonomous systems.
The BGP can in fact be conceptually separated into two distinct protocols—External BGP (or E-BGP), which is the protocol used for exchanging external routing information among different autonomous systems, and Internal BGP (or I-BGP), which is the protocol used for exchanging this external routing information among routers within the same AS. (Although the RFC which defines the BGP does not explicitly refer to the external and internal versions of BGP as E-BGP and I-BGP, respectively, this terminology is in common usage by those of ordinary skill in the art when referring to the two uses of BGP.)
In U.S. patent application Ser. No. 09/583,595, “Method and Apparatus for Exchanging Routing Information in a Packet-Based Data Network”, filed by T. G. Griffin and G. T. Wilfong on May 31, 2000, a novel routing protocol, referred to as the Simple Path Vector Protocol (SPVP), is disclosed. SPVP extends the E-BGP by adding a new attribute to the routing messages sent by an edge router to its peers in different autonomous systems. This additional attribute is a path history which is dynamically computed at each edge router as the routing path to a particular destination is changed, and which is then sent by the router to its peers together with the sending router's path to that destination. Noting that protocol oscillations caused by policy conflicts produce paths whose histories contain cycles, by observing the dynamic path history that is computed at an edge router as a received routing message from a peer router that contains a history attribute is processed, a cycle can be identified in the newly computed history and associated with a policy conflict at that receiving edge router's associated autonomous system. Thus, SPVP can automatically and advantageously suppress as a permitted path to that destination those paths whose histories contain cycles, thereby solving the route oscillation problem in E-BGP. U.S. patent application Ser. No. 09/583,595, which is commonly assigned to the assignee of the present invention, is hereby incorporated by reference as if fully set forth herein.
It has also been observed, however, that route oscillations can occur when using I-BGP as well, particularly when “route reflection” or “confederation” I-BGP architectures are employed within an AS. (See, e.g., Cisco Systems, Endless BGP Convergence Problem in Cisco IOS Software Releases, Cisco Systems Inc. Field Notice, Oct. 10, 2000.) (Route reflection I-BGP architectures and confederation I-BGP architectures are alternatives to a full mesh I-BGP architecture, in which every I-BGP router shares routing information with every other I-BGP router in a given AS. These architectures are conventional and fully familiar to those skilled in the art—see, e.g., T. Bates and R. Chandra, BGP Route Reflection: An Alternative to Full Mesh I-BGP, RFC 1966, 1996.) That is, some subset of the routers within an AS may exchange routing information forever without being able to settle on a stable routing configuration. This happens when no stable routing configuration exists (or when such a stable configuration is unachievable). Such a route oscillation is referred to as a persistent route oscillation.
Moreover, another kind of route oscillation—transient route oscillation—can also occur in such a system. In this case, some subset of routers may undergo route oscillations due to a timing coincidence, such as, for example, message delays or a particular order in which the routers send and receive messages. These route oscillations are transient in nature because they will typically disappear when the timing coincidence no longer exists. Nonetheless, they can result in significant Internet performance bottlenecks until the time that they do resolve.